#include <algorithm>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <ostream>
#include <sstream>
#include <string>
#define lld long long // long long 的printf 占位符是lld
#define ENDL '\n'     // 将 endl 替换为 \n 取消缓冲区
const long long MAX_ = 1e9;
using std::cin;
using std::cout;
using std::endl;
using std::string;

lld X[33], Y[33];

lld gcd(lld x, lld y) {
  if (y == 0) {
    return x;
  } else {
    return gcd(y, x % y);
  }
}
lld lcm(lld x, lld y) { return x * y / gcd(x, y); }

void solve() {

  memset(X, 0, sizeof(X));
  memset(Y, 0, sizeof(Y));

  lld a, b, c, d;
  lld count = 0;
  cin >> a >> b >> c >> d;
  for (int i = 1; i <= 32; ++i) {
    X[i] = a * X[i - 1] + b;
    Y[i] = c * Y[i - 1] + d;
  }

  if (a == 1 and c == 1) {
    count = MAX_ / lcm(b, d);
    // linear
  } else if (a != 1 and c == 1) {
    // X:inear and Y;exp
    for (int i = 1; X[i] <= MAX_; ++i) {
      if (X[i] % d == 0 and X[i] / d >= 1)
        count++;
    }
  } else if (a == 1 and c != 1) {
    // Y:linear and x:exp

    for (int i = 1; Y[i] <= MAX_; ++i) {
      if (Y[i] % b == 0 and Y[i] / b >= 1)
        count++;
    }
  } else {
    for (int i = 1; i <= 32; ++i) {
      if (X[i] > MAX_)
        break;
      for (int j = 1; j <= 32; ++j) {
        if (Y[j] > MAX_)
          break;
        if (X[i] == Y[j]) {
          count++;
          break;
        }
      }
    }
  }
  cout << count << ENDL;
}
int main() {
  int T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
}